The following relates to wireless networks. It finds particular application with the establishment of secure communication of information within a wireless body sensor network. However, it is to be appreciated that the invention may also find application in providing secure communication between other wireless devices and other wireless transponders.
Mobile body sensor networks (BSNs) have received attention for medical applications and are generally used for patient care and monitoring. A BSN includes data-collection nodes and optionally control nodes. Sensor nodes are battery powered, have limited computational capabilities and memory, and rely on intermittent wireless communication via radio frequency. Conventionally, a large group (e.g., thousands) of interoperable nodes are deployed in a medical area such as a hospital and then, by different means, spontaneously join to form different disconnected BSNs. The BSN is usually composed of a small subset (from 2 to 50 nodes) of all the nodes, e.g., the nodes assigned with an individual patient in the medical area. A priori, the size and membership of a BSN is unknown: BSN nodes may be present at the moment of BSN formation or may be added and deleted subsequently. Some nodes have limited mobility after formation of the BSN and others are highly mobile and often roam through different independent BSNs formed in the same area (e.g., data collection and control nodes carried by human users, sensors worn by persons, etc.). Some nodes might be left unattended. The lifetime of a BSN is limited to a few days, weeks, months, etc. The lifetime of sensor nodes typically is longer than the lifetime of a BSN instance. The BSN is formed in public or hostile areas where communication can be monitored and sensor nodes are subject to capture and manipulation by an unscrupulous individual. Cross talk between the nodes of BSNs associated with different patients could compromise the medical validity of the sensed data.
These challenging operational requirements place equally challenging security constraints on BSN design. Security services for BSN include authentication and communication confidentiality. Typically, key management services provide and manage the basic security material for satisfying the previously mentioned security services. The computational and communication constraints of BSN sensor nodes make it impractical to use any security solution based on public key cryptography. The ad hoc nature of BSNs and the operational requirements of BSN make typical online server-based solutions inappropriate.
Key management based on key pre-distribution schemes (KPS) is the one option for BSNs. The need for unique node authentication and key establishment, independently of the BSN membership and size, imposes strict requirements on a KPS for BSNs. However, existing KPS proposals are limited for BSNs. First, network wide key pre-distribution does not offer enough security or cannot be managed in BSNs. Second, trivial KPS is neither scalable nor manageable in BSNs. Third, the resiliency and scalability of Blundo's KPS (Perfectly Secure Key Distribution for Dynamic Conferences. In Advances in Cryptology—CRYPTO '92, Springer-Verlag, Berlin, 1993, pp. 471-486) is limited by the memory and computational power of sensor nodes. Fourth, random key pre-distribution does not offer good connectivity properties for BSN with a limited number of nodes. Finally, çamtepe and Yener deterministic KPS based on combinatorial design theory (Combinatorial Design of Key Distribution Mechanisms for Wireless Sensor Networks. In Proc. of Computer Security-ESORICS, Springer-Verlag, LNCS 3193, 2004, pp 293-308) has compatible connectivity properties and moderate resilience for BSNs but does not provide unique pairwise keys.
Basagni et al. (Secure pebblenets. In Proc. of the 2nd ACM International Symposium on Mobile Ad Hoc Networking and Computing, pp. 156-163. 2001) presents a key management scheme to secure sensor communications by periodically updating the group symmetric key shared by all the sensor nodes. This scheme assumes tamper-resistant sensors and a distributed sensor network (DSN) wide connected management infrastructure, assumptions that are not applicable for BSNs (A large-scale DSN can be viewed as the interconnection of multiple BSNs with singular operational and networking differences. Alternatively, BSNs are seen as multiple disconnected splits of a large-scale DSN).
Perrig et al. (SPINS: Security protocols for sensor networks. In Proc. of MOBICOM, 2001) proposes SPINS, a security architecture specifically designed for sensor networks. In SPINS, each sensor node shares a secret key with the base station. Two sensor nodes cannot directly establish a secret key. However, they can use the base station as a trusted third party to set up the secret key. In BSNs, a base station may not be available at the moment of key establishment.
Blundo et al. proposes a polynomial-based KPS to derive group keys. For groups of two users, Blundo's key pre-distribution scheme can be used to establish pairwise keys in BSNs. A set-up server randomly generates a symmetric bivariate λ-degree polynomial
      f    ⁡          (              x        ,        y            )        =            ∑              i        ,                  j          =          0                    λ        ⁢                  a        ij            ⁢              x        i            ⁢              y        j            over a finite field Fq wherein q is a prime number large enough to accommodate a cryptographic key. By the property of symmetry f(x,y)=f(y,x). The setup server computes and distributes a polynomial share of f(x,y) to for each sensor u, i.e. f(u,y). Each sensor u has a unique identifier. After the deployment phase, for two arbitrary nodes u and v, node u can compute the common key Kuv=f(u,v) by evaluating f(u,y) at point v, and node v can compute the same key Kuv=f(v,u)=f(u,v) by evaluating f(v,y) at point u.
The resiliency, α, of a Blundo's KPS is α=λ+1, i.e. an attacker needs to compromise α sensors to be able to generate pairwise keys of non-compromised sensors. Each sensor node u requires storing a λ-degree polynomial share f(u,y), which occupies (λ+1)log q storage space. It is to be appreciated that λ is limited by the memory m available on sensors, i.e. m≧λ+1 keys. There is no communication overhead during the pairwise key establishment process. To establish a pairwise key, both sensor nodes need to evaluate the polynomial at the ID of the other sensor node. This requires λ modular multiplications and λ modular additions in Fq, which can be costly in sensors with limited CPU capabilities.
Liu et al. (Establishing pairwise keys in distributed sensor networks. In Proc. of the 10th ACM Conference on Computer and Communications Security (CCS), 2003, pp. 52-61) describe a modification of polynomial evaluation to adapt to the restrictions imposed by low-bit CPUs with no division instruction and thus reduce computation requirements on sensors. This is achieved by reducing the length in bits of the coefficients of a λ-degree bivariate polynomial to log q′ and by choosing q′ of the form q′=2k+1.
Liu et al. demonstrate that a key of log q bits can be compounded by concatenating the t partial keys generated with t λ-degree bivariate polynomial shares {fi(u,y)}i=1, . . . t with coefficients on Fq′, where t=└log q/log q′┘, without a significant loss of security, i.e. the resulting log q-bit key possesses similar entropy as it had been generated with a λ-degree bivariate polynomial with coefficients on Fq. A joint set of t λ-degree bivariate polynomials {fi(x,y)}i=1, . . . t with coefficients on Fq′ is referred to a t-polynomial-set Fi(x,y). The t-polynomial-set Fi(u,y) evaluated at point u hereafter is a t-polynomial-set share.
The downside of this technique is that a polynomial over Fq′ can only accommodate a maximum of q′−1 sensors (instead of q−1). Particularly, t polynomials over Fq′ combined in parallel (i.e. a t-polynomial-set) can only accommodate a maximum of N′=q′−1 nodes. For instance, for 8-bit CPUs, q′=28+1 offers optimal computational performance but, then, the number N′ of maximum nodes is 256. A property still holding is that each bivariate polynomial {fi(x,y)}i=1, . . . t, over Fq′, and, thus, a t-polynomial-set, is λ-collusion resistant. The polynomial split technique can be applied to any polynomial-based KPS, under certain lower bound on λ imposed by q, q′ and the total number of polynomials over Fq′ used by the KPS.
A balanced incomplete block design (BIBD) is an arrangement of v distinct objects into b blocks such that each block contains exactly k distinct objects, each object occurs in exactly r different blocks, and every pair of distinct objects occurs together in exactly t blocks. The design can be expressed as (v, k, t), or equivalently (v, b, r, k, t), where: t(v−1)=r(k−1) and bk=vr.
In a symmetric BIBD (SPIBD) b=v and, thus, k=r. A SPIBD has four properties: every block contains k=r elements, every element occurs in k=r blocks, every pair of elements occurs in t blocks and every pair of blocks intersects in t elements.
Given a block design D=(v, k, t) with a set S of |S|=v objects and a set B={B1, B2, . . . Bb} of |B|=b blocks where each block includes exactly k objects, a complementary design D has the complement blocks Bi=S−Bi as its blocks for 1≦i≦b. D is a BIBD with parameters (v,b,b−r,v−k,b−2r+t), where b−2r+t>0. If D=(v,k,t) is an SBIBD, then D is also an SBIBD.
Finite Projective Planes (FPP) is a subset of SPIBDs of special interest for key pre-distribution. An FPP is an SPIBD with parameters (n2+n+1, n+1,1). An FPP exists for any prime power n, where n≧2. FPP of order n has four properties: (i) every block contains exactly n+1 points, (ii) every point occurs on exactly n+1 blocks, (iii) there are exactly n2+n+1 points, and (iv) there are exactly n2+n+1 blocks. çamtepe and Yener (Combinatorial Design of Key Distribution Mechanisms for Wireless Sensor Networks. In Proc. of Computer Security-ESORICS, Springer-Verlag, LNCS 3193, 2004, pp 293-308) apply SBIBD design for key pre-distribution in SNs.
Assume an FPP with parameters (n2+n+1, n+1,1), with elements belonging to a set S, where |S|=n2+n+1. Using Eschenauer and Gligor (A key-management scheme for distributed sensor networks. In Proc. of the 9th ACM conference on Computer and communications security, pp. 41-47, 2002) terminology, S is associated with a key pool i.e. each element in S is associated with a distinct random key. Further, each block of FPP is associated with a key ring. The properties of FPPs guarantee that any pair of key rings (blocks) has 1 random key (element) in common.
For a sensor network (SN) of N nodes, with total of N key rings, an FPP with n2+n+1≧N blocks needs to be constructed by using set S. That provides n2+n+1≧N key rings each having K=n+1 keys and one key in common. The memory size required on nodes is then (n+1)×log q (equivalently m=n+1). A wise attacker needs to capture α=K=n+1 nodes to be able to compromise the SN.
Each sensor node of an N-population SN receives a different key ring. Observe that every two nodes share a specific key in common. Actually, because of the properties of FPPs, each n+1 sensors share the same specific key. Consequently, the keys of this KPS cannot be used for node unique authentication. A second related problem is that it is not always possible to find an FPP in which (i) n is a prime power and (ii) n2+n+1≧N, with the limitation m≧n+1.
çamtepe and Yener solve the above problem by constructing a Hybrid Design, which includes n2+n+1 blocks of an FPP (n2+n+n1, n+1,1) where n<m−1 (i.e. now the size of the key ring m≧K>n+1) and N−n2+n+1 arbitrarily selected (n+1)-element sub-blocks of FPP (n2+n+1, n2, n2−n). The side effects are: (i) K>n+1, (ii) some specific keys are shared by more than n+1 nodes, (iii) some pairs of nodes may share up to n2−n keys in common and (iv), at least N−n2+n+1 blocks do not have a key in common. Thus, because of (iv), at least N−n2+n+1 cannot directly establish a common key, and because of (i), (ii), and (iii), α≦n+1<K≦m, i.e. the network resiliency lowers.
Recently, a number of random key management schemes based on key pre-distribution have been proposed for securing the communication infrastructure of large-scale DSN. Such management schemes assume DSN-wide connectivity based on the assumptions that a sensor node is able to wirelessly connect to a minimum degree of neighbor nodes (e.g., nodes in wireless communication range) and that sensor nodes have very restricted mobility after deployment. These schemes aim at maximum DSN-wide secure connectivity and network resiliency yet satisfying operational constraints of DSNs. In random key pre-distribution schemes each node receives, before deployment, a random subset of keys from a large key pool. To agree on a key for secure communication with certain probability, two neighbor nodes find one common key within their subsets and use that key as their shared secret key. Two sensor nodes, which do not find a common key, make use of other trusted nodes in their neighborhood or even some hops away to help establishing a common key. Random pairwise key pre-distribution schemes based on Blom's (An optimal class of symmetric key generation systems. In Proc. of the EUROCRYPT 84 workshop on Advances in cryptology: theory and application of cryptographic techniques, pp. 335-338, 1985) or Blundo's schemes enhance the former by increasing network resiliency and additionally providing for node authentication.
However, random key pre-distribution schemes are not suited to secure BSNs. First, due to the small degree of neighboring nodes, the BSN does not always enable two arbitrary nodes to directly or indirectly establish a common key. Second, due to the possibility of node captures, node authentication should be performed directly without any intermediaries.
Since independent BSNs are not interconnected, centralized or distributed global intrusion detection systems (IDS) suggested for DSNs or for ad hoc networks cannot be used in BSNs. A compromised node might be detected in a BSN, but conventional systems and methods do not efficiently distribute this information to the rest of nodes in other BSNs. Therefore, BSNs are far more vulnerable to node replication attacks than a large-scale DSN. In hospitals, for example, attacks from the smart attacker are the largest threat for BSN security. Although not clearly stated in literature, network resiliency against node captures and node replication of former key pre-distribution schemes highly depends on the existence of a DSN-wide effective IDS. Iresiliency of the network is defined as a number λ of nodes that an attacker needs to capture to compromise a fraction of total DSN communications. A smart attacker does not bother capturing and tampering λ nodes to mount an attack. The smart attacker just captures one or a small fraction of nodes and uses the compromised keys to attack the network. Actually, to go undetected, the attacker does not try to disrupt the network operations of the network, but attempts to read or modify confidential information or even inject false messages. In this manner, the attacker may acquire and/or inject the desired information without even having to waste their own resources to compromise other network communications.
Finally, the key establishment mechanism assisted by neighbors is needed in some schemes to achieve a high degree of secure DSN connectivity. An attacker with the appropriate keys can obtain assistance from one or more adjacent nodes, nodes adjacent to such nodes, and so on to establish keys with the complete neighborhood. If secure connectivity is sacrificed to improve security by restricting the key establishment assistance to the node's neighborhood, the attacker is still able to move and try to attack as many neighborhoods as possible. An effective and secure key management scheme must consider the smart attacker, especially in BSN settings.
What is needed is a key pre-distribution scheme that enables authentication, confidentiality and integrity services and provides increased network secure connectivity, resiliency and scalability coupled with optimal performance efficiency. It is also needed a key management scheme, which controls usage of pre-distributed keys, suitable for the operational conditions of BSNs. The present invention contemplates an improved apparatus and method that overcomes the aforementioned limitations and others.